#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <string>
using namespace std;
// 表达式可以对应一个树结构，称为表达式树。
//其中的叶结点对应表达式中的操作数，非叶结点对应运算符，假定所有运算均为二元运算。
//根据后缀表达式可以构造出表达式二叉树，方法是：从左向右扫描后缀表达式，每扫描到一个符号就生成一个二叉树结点，该符号作为结点的数据域值；
//若扫描到的符号是操作数，则将此操作数结点压栈；若扫描到的符号是运算符，则从栈中弹出两个结点，分别作为当前运算符结点的右、左孩子，//
//再将当前运算符结点压栈。表达式扫描完成后，栈顶即为表达式树的根结点。表达式树的后根序列即为后缀表达式。
// 现给定一个后缀表达式exp，请编写程序求出exp的“最右子表达式”。exp的“最右子表达式”是指从exp对应的表达式树右边看向树，从第0层到最底层所能看到的各结点。例如后缀表达式abcdef+−g+∗−h∗+对应的表达式树如图1所示，其最右子表达式为 +∗h∗+g+f 
struct treenode{
    char data;
    treenode *left;
    treenode *right; 
    treenode(char val = 0) : data(val), left(nullptr), right(nullptr) {} // 构造函数
};

// 递归删除树
void deleteTree(treenode* root){
    if(root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

// 获取“最右子表达式”
string getRightexp(treenode* root){
    if(root == nullptr) return "";
    string rightexp = "";
    queue<treenode*> q;
    q.push(root);
    while(!q.empty()){
        int size = q.size();
        treenode* current = nullptr;
        for(int i = 0; i < size; i++){
            current = q.front(); q.pop();
            if(current->left) q.push(current->left);
            if(current->right) q.push(current->right);
        }
        if(current != nullptr){
            rightexp += current->data;
        }
    }
    return rightexp;
}

int main(){
    int n;
    cin >> n;
    char a[505];
    for(int i = 1; i <= n; i++){
        cin >> a;
         treenode *root = NULL;
        int length = strlen(a);
        stack<treenode*> s; 
        for(int j = 0; j < length; j++){
            if(a[j] >= 'a' && a[j] <= 'z'){
                treenode *b = new treenode(a[j]);
                s.push(b);
            }
            if(a[j] >= 'A' && a[j] <= 'Z'){
                treenode *c1 = s.top(); s.pop();
                treenode *c2 = s.top(); s.pop();
                treenode *b = new treenode(a[j]);
                b->left = c2;
                b->right = c1;
                s.push(b);
            }
        }
        root = s.top(); s.pop();
        // 计算“最右子表达式”
        string rightView = getRightexp(root);
        cout << rightView << endl;
        // 释放树的内存
        deleteTree(root);
    }
    return 0;
}
